package com.wangjie.diffarray;

import java.util.Arrays;

/**
 * @author jieshao
 * @date 2022/4/8 14:01
 *
 * 1109. 航班预订统计
 */
public class Test03 {
    public static void main(String[] args) {
        int[][] arr = {{1, 2, 10}, {2, 3, 20}, {2, 5, 25}};
        int length = 5;
        int[] result = corpFlightBookings(arr, length);
        System.out.println(Arrays.toString(result));
    }

    public static int[] corpFlightBookings(int[][] bookings, int n) {
        // 差分数组和结果数组用的同一个
        int[] res = new int[n];
        for (int[] booking : bookings) {
            int i = booking[0];
            int j = booking[1];
            int val = booking[2];
            // 构造差分数组(给闭区间 [i, j] 增加 val)
            res[i - 1] += val;
            if (j < n) {
                res[j] -= val;
            }
        }

        // 还原结果数组
        for (int i = 1; i < n; i++) {
            res[i] += res[i - 1];
        }

        return res;
    }
}